package org.dubh.dp;

import static com.google.common.base.Preconditions.*;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;


/**
 * Implementation of a classic dynamic programming solution to the unbounded
 * knapsack problem.<p>
 *
 * Say we have a knapsack with capacity C, and a collection of n item types i,
 * each of which has cost ci and value vi. The unbounded knapsack problem
 * maximizes the value vi of items in the knapsack with the constraint that the
 * sum of the costs does not exceed C.<p>
 *
 * Dynamic programming solves this problem in O(Cn). This implementation has
 * space complexity O(C).
 * 
 * @author brian.duff@dubh.org
 */
public final class Knapsack {
    
    private final int capacity;
    
    /**
     * Constructs a knapsack.
     * 
     * @param capacity the capacity of the knapsack. Must be more than 0.
     */
    public Knapsack( int capacity ) {
        checkArgument( capacity > 0, "capacity must be greater than zero: " + capacity );        
        this.capacity = capacity;
    }
    
    /**
     * Returns a collection of items that optimizes the value of the knapsack
     * without exceeding its capacity.
     * 
     * @param items a collection of available item types.
     * @return a collection of items. Items may be duplicated.
     */
    public Collection<KnapsackItemType> optimizeContents( List<KnapsackItemType> items ) {
        checkNotNull( items, "items must not be null" );
        checkArgument( items.size() > 0, "must have at least one item" );

        int[] valueSum = new int[ capacity + 1 ];
        int[] itemIndex = new int[ capacity + 1 ];
        int[] previousSumIndex = new int[ capacity + 1 ];
        
        for ( int i=1; i <= capacity; i++ ) {
            int max = 0;
            for ( int j=0; j < items.size(); j++ ) {
                KnapsackItemType item = items.get( j );
                if ( item.cost() > i ) continue;
                int value = item.value() + valueSum[ i - item.cost() ];
                if ( value > max ) {
                    valueSum[ i ] = value;
                    itemIndex[ i ] = j;
                    previousSumIndex[ i ] = i - item.cost();
                    max = value;
                }
            }
        }
        
        // Backtrack to find the actual items for the optimal solution. Note
        // that this is at worst O(C), so does not effect the overall complexity
        // of the algorithm.
        Collection<KnapsackItemType> knapsackItems = new ArrayList<KnapsackItemType>();
        int i = capacity;
        while ( i > 0 ) {
            knapsackItems.add( items.get( itemIndex[i] ) );
            i = previousSumIndex[ i ];
        }
        
        return Collections.unmodifiableCollection( knapsackItems );
    }
    
    @Override
    public String toString() {
        return String.format( "Knapsack[capacity=%s]", capacity );
    }
}
